package leetcode_bin_tree_test;

import bin_tree_order.Main.TreeNode;

/**
 * 二叉树的坡度
 */
public class Slope {
    public int findTilt(TreeNode root) {
        // 整个树 的坡度就是其所有节点的坡度之和
        if (root == null) {
            return 0;
        }
        int sumTilt = 0; // 所有节点的坡度之和
        int left = sumKid(root.left);
        int right = sumKid(root.right);
        sumTilt += Math.abs(left - right);
        return sumTilt + findTilt(root.left) + findTilt(root.right);
    }

    /**
     * 计算子树上所有节点的值的和
     * @param kidRoot
     * @return
     */
    public int sumKid(TreeNode kidRoot) {
        if (kidRoot == null) {
            return 0;
        }
        int sum = kidRoot.val;
        int left = sumKid(kidRoot.left);
        int right = sumKid(kidRoot.right);
        return sum + left + right;
    }
}
